#include <geekos/malloc.h>
#include <geekos/string.h>
#include <geekos/defs.h>
#include <geekos/mem.h>
#include <geekos/int.h>
#include <geekos/gdt.h>
#include <geekos/sort.h>

//归并排序
void copyArray(Elf32_Addr *source, Elf32_Addr *dest, int len, int first)  
{  
    int i;  
    int j=first;  
    for(i = 0; i<len; i++)  
    {  
        dest[j] = source[i];  
        j++;  
    }  
          
}

//相邻两个有序子序列的归并函数，将a[low...mid]和a[mid+1...high]归并到T[LOW..high]中 
void merge(Elf32_Addr *a, int left, int right)  
{  
    int begin1 = left;  
    int mid = (left+right)/2 ;  
    int begin2 = mid+1;  
    int k = 0;  
    int newArrayLen = right-left+1;  
    Elf32_Addr *b = (Elf32_Addr*)Malloc(newArrayLen * sizeof(Elf32_Addr));  
    while(begin1 <= mid && begin2 <= right)  
    {  
        if(a[begin1] <= a[begin2])  
            b[k++] = a[begin1++];  
        else  
            b[k++] = a[begin2++];  
    }  
    while(begin1 <= mid)  
        b[k++] = a[begin1++];  
    while(begin2 <= right)  
        b[k++] = a[begin2++];  
    copyArray(b, a, newArrayLen, left);  
    Free(b);  
}

//归并函数,将a[low...high]归并到T[low...high]中
void mergeSort(Elf32_Addr *a, int left, int right)  
{  
    int i;  
    // 保证至少有两个元素  
    if(left < right)  
    {  
        i = (left + right)/2;  
        mergeSort(a, left, i);  
        mergeSort(a, (i + 1), right);  
        merge(a, left, right);  
    }  
}

void MergeSort(Elf32_Addr *a, int n)
{
	mergeSort(a, 0, (n - 1));
}